package com.linyaonan.leetcode.medium._2131;

import java.util.HashMap;
import java.util.Map;

/**
 * 给你一个字符串数组 words 。words 中每个元素都是一个包含 两个 小写英文字母的单词。
 *
 * 请你从 words 中选择一些元素并按 任意顺序 连接它们，并得到一个 尽可能长的回文串 。每个元素 至多 只能使用一次。
 *
 * 请你返回你能得到的最长回文串的 长度 。如果没办法得到任何一个回文串，请你返回 0 。
 *
 * 回文串 指的是从前往后和从后往前读一样的字符串。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：words = ["lc","cl","gg"]
 * 输出：6
 * 解释：一个最长的回文串为 "lc" + "gg" + "cl" = "lcggcl" ，长度为 6 。
 * "clgglc" 是另一个可以得到的最长回文串。
 * 示例 2：
 *
 * 输入：words = ["ab","ty","yt","lc","cl","ab"]
 * 输出：8
 * 解释：最长回文串是 "ty" + "lc" + "cl" + "yt" = "tylcclyt" ，长度为 8 。
 * "lcyttycl" 是另一个可以得到的最长回文串。
 * 示例 3：
 *
 * 输入：words = ["cc","ll","xx"]
 * 输出：2
 * 解释：最长回文串是 "cc" ，长度为 2 。
 * "ll" 是另一个可以得到的最长回文串。"xx" 也是。
 *  
 *
 * 提示：
 *
 * 1 <= words.length <= 105
 * words[i].length == 2
 * words[i] 仅包含小写英文字母。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/longest-palindrome-by-concatenating-two-letter-words
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Solution {
    public int longestPalindrome(String[] words) {

        HashMap<String, Integer> aaMap = new HashMap<>();
        HashMap<String, Integer> abMap = new HashMap<>();

        int abGroup = 0;

        // 首先将字符数组进行分组，将第一位与第二位相同的进行分组，不同的进行分组
        for (String word : words) {
            char[] chars = word.toCharArray();
            if (chars[0] == chars[1]) {
                Integer thisAACount = aaMap.getOrDefault(word, 0);
                aaMap.put(word, thisAACount + 1);
            } else {
                String r = "" + chars[1] + chars[0];
                if (abMap.containsKey(r)) {
                    abGroup++;
                    Integer integer = abMap.get(r);
                    if (integer == 1) {
                        abMap.remove(r);
                    } else {
                        abMap.put(r, --integer);
                    }
                } else {
                    abMap.put(word, abMap.getOrDefault(word, 0) + 1);
                }
            }
        }

        String maxAA = null;
        int maxAAC = 0;

        int r = 0;
        // 找到最大的aa字符以及个数
        for (Map.Entry<String, Integer> entry : aaMap.entrySet()) {
            Integer value = entry.getValue();
            // 最大的奇数
            if (value > maxAAC && ((value & 1) == 1)) {
                maxAA = entry.getKey();
                maxAAC = value;
            }
        }
        r += maxAAC * 2;
        if (maxAA != null) {
            aaMap.remove(maxAA);
        }

        for (Map.Entry<String, Integer> entry : aaMap.entrySet()) {
            Integer value = entry.getValue();
            if (value >= 2) {
                if ((value % 2 == 0)) {
                    r += value * 2;
                } else {
                    r += (value - 1) * 2;
                }
            }
        }

        return r + abGroup * 4;

    }
}